Формула Стирлинга

Для более точных оценок есть **формула Стирлинга**: $$n! \sim \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n$$

Оценим центральный биномиальный коэффициент (для $n$ четного) с помощью формулы Стирлинга: $$\binom{n}{n/2} = \frac{n!}{(n/2)!(n/2)!} \sim \frac{\sqrt{2\pi n} \cdot (\frac{n}{e})^n}{\sqrt{\pi n} \cdot (\frac{n/2}{e})^{n/2} \sqrt{\pi n} \cdot (\frac{n/2}{e})^{n/2}} = \sqrt{\frac{2}{\pi n}} \cdot 2^n$$

Еще одна оценка (с использованием формулы Стирлинга): $$\binom{n}{n/3} = \frac{n!}{(n/3)!(2n/3)!} \sim \frac{\sqrt{2\pi n} \cdot (\frac{n}{e})^n}{\sqrt{\frac{2\pi n}{3}} \cdot (\frac{n/3}{e})^{n/3} \sqrt{\frac{4\pi n}{3}} \cdot (\frac{2n/3}{e})^{2n/3}} = \frac{3}{2} \sqrt{\frac{1}{\pi n}} \cdot \left(\frac{3}{\sqrt[3]{4}}\right)^n$$ Заметим, что $\left(\frac{3}{\sqrt[3]{4}}\right)^n \approx 1.89^n \ll 2^n$